import java.util.ArrayList;
import java.util.List;

public class L17 {
    public static void main(String[] args) {
        List<String> strings = new Solution().letterCombinations("23");
        System.out.println(strings.toString());

    }


    static class Solution {
        List<String> result = new ArrayList<>();

        public List<String> letterCombinations(String digits) {
            if (digits.isEmpty()) {
                return result;
            }

            char[] chars = digits.toCharArray();

            List<char[]> start = new ArrayList<>();
            for (int i = 0; i < chars.length; i++) {
                start.add(get(chars[i]));
            }

            if (start.size() == 0) {
                return result;
            }
            char[] tmp = new char[start.size()];

            backTracking(start, tmp, 0);
            return result;
        }

        private void backTracking(List<char[]> start, char[] tmp, int index) {
            if (index == start.size()) {
                result.add(new String(tmp));
                return;
            }

            char[] chars = start.get(index);
            for (int i = 0; i < chars.length; i++) {
                tmp[index] = chars[i];
                backTracking(start, tmp, index + 1);
            }


        }

        private char[] get(char aChar) {
            switch (aChar) {
                case '2':
                    return new char[]{'a', 'b', 'c'};
                case '3':
                    return new char[]{'d', 'e', 'f'};
                case '4':
                    return new char[]{'g', 'h', 'i'};
                case '5':
                    return new char[]{'j', 'k', 'l'};
                case '6':
                    return new char[]{'m', 'n', 'o'};
                case '7':
                    return new char[]{'p', 'q', 'r', 's'};
                case '8':
                    return new char[]{'t', 'u', 'v'};
                case '9':
                    return new char[]{'w', 'x', 'y', 'z'};
                default:
                    return new char[0];

            }
        }
    }
}
